/*
 * @lc app=leetcode.cn id=215 lang=cpp
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start
class Solution {
public:
    int quickSelect(vector<int>& nums, int lo, int hi, int index) {
        int q = randomPartition(nums, lo, hi);
        if (q == index) {
            return nums[q];
        } else {
            return q < index ? quickSelect(nums, q + 1, hi, index) : quickSelect(nums, lo, q - 1, index);
        }
    }

    inline int randomPartition(vector<int>& nums, int lo, int hi) {
        int i = rand() % (hi - lo + 1) + lo;
        swap(nums[i], nums[hi]);
        return partition(nums, lo, hi);
    }
    
    inline int partition(vector<int>& nums, int lo, int hi) {
        int povit = nums[hi];
        int i = lo - 1;
        for (int j = lo; j <= hi-1; ++j) {
            if (nums[j] <= povit) {
                i += 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i+1], nums[hi]);
        return i+1;
    }

    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        return quickSelect(nums, 0, nums.size()-1,nums.size()-k);
    }
};
// @lc code=end

